CF26D Tickets

不妨设n+k>=mn+k>=m , 且$ n < m $。

回忆一下卡塔兰数的推导过程 , 我们用类似的方法解决此题。

首先,我们可将题意转化成从(0,0)(0,0)(n,m)(n,m)不穿过y=x+ky=x+k的一条路径。

y=x+ky=x+k向上平移一个单位得y=x+k+1y=x+k+1(黄色的函数),原题等价于求一条路径且不经过y=x+k+1y=x+k+1的路径。

从反面思考,我们只需找到经过y=x+k+1y=x+k+1的路径即可。

我们不妨将A(0,0)A(0,0)关于y=x+k+1y=x+k+1作对称得到A(k1,k+1)A'(-k-1,k+1),发现对于每一条ABA' \to B的路径,都会穿过y=x+k+1y=x+k+1 , 且一定有一条ABA \to B的路径与之对应。(蓝色虚线与红色实线)

那么经过y=x+k+1y=x+k+1的路径的数量为Cn+mn+k+1C_{n+m}^{n+k+1}

又因为从起点到终点的路径一共有Cn+mnC_{n+m}^{n}

所以答案为1Cn+mn+k+1Cn+mn1-\frac{C_{n+m}^{n+k+1}}{C_{n+m}^{n}}

还有两种特殊情况:

1.k>=mk>=m , 此时直接输出11

2.n+k<mn+k<m , 此时直接输出00

这道题的n,mn,m都很大,建议用自然对数的形式存阶乘。

#include <cstdio>
#include <cmath>

const int MAXN = 300000; 
int n , m , k;
double Ans , Fac[ MAXN + 5 ];

void Init( ) {
	Fac[ 0 ] = 0;
	for( int i = 1 ; i <= MAXN ; i ++ )
		Fac[ i ] = Fac[ i - 1 ] + log( i * 1.0 );
}
double C( int n , int m ) {
	return Fac[ n ] - Fac[ m ] - Fac[ n - m ];
}

int main( ) {
	Init( );
	scanf("%d %d %d",&n,&m,&k);
	if( k >= m ) 
		Ans = 1;
	else if( n + k < m ) 
		Ans = 0;
	else
		Ans = 1 - exp( C( n + m , n + k + 1 ) - C( n + m , n ) );
	printf("%.6lf",Ans);
	return 0;
}